package ru.eas.multiplication;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author aesipov
 */
public class KaratsubaMultiplicationListImpl {

    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        String xString  = scanner.next();
//        String yString = scanner.next();
//        String xString = "239030239030566179";
//        String yString = "56617956617923930";
        String xString = readData();
        String yString = readData();

        long p_1 = System.currentTimeMillis();

        int[] x = getNumberList(xString);
        int[] y = getNumberList(yString);

        IntArray result = karatsuba(new SimpleIntArray(x), new SimpleIntArray(y), 1000000000);
        long p_2 = System.currentTimeMillis();
        System.out.println("common = " + (p_2 - p_1));

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < result.size(); i++) {
            String str = String.valueOf(result.get(i));
            if (i != 0) {
                for (int j = 0; j < 9 - str.length(); j++) {
                    sb.append("0");
                }
            }
            sb.append(str);
        }
        System.out.println(sb.toString());
//        System.out.println("13533403703804583268316967452763470");
    }

    private static int[] getNumberList(String numberString) {
        int length = numberString.length() % 9 == 0 ? numberString.length() / 9 : 1 + numberString.length() / 9;
        int[] result = new int[length];
        int index = result.length - 1;
        for (int i = numberString.length(); i >= 0 ; i = i - 9) {
            int left = i - 9;
            int right = i;
            if (left > 0) {
                result[index] = Integer.valueOf(numberString.substring(left, right));
                index--;
            } else {
                result[index] = Integer.valueOf(numberString.substring(0, right));
                break;
            }
        }
        return result;
    }

    private static String readData() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 100000; i++) {
            sb.append(9);
        }
        return sb.toString();
    }

    private static IntArray karatsuba(IntArray x, IntArray y, int radix) {
        long p_1 = System.nanoTime();

//        System.out.println("x = " + Arrays.toString(x.toArray()));
//        System.out.println("y = " + Arrays.toString(y.toArray()));

        int n = Math.max(x.size(), y.size());

        if (n <= 1) {
            long p_2 = System.nanoTime();

            long xLong = byteArrayNumberToLong(x, radix);
            long yLong = byteArrayNumberToLong(y, radix);
            IntArray result = longNumberToByteArray(xLong * yLong, radix);

//            System.out.println("r = " + Arrays.toString(result.toArray()));
            long p_3 = System.nanoTime();
//            System.out.println("p3 = " + (p_3 - p_2));
            return result;
        }

        int floorHalfN = n / 2;

        IntArray  xLeft = getLeft(x, floorHalfN);
        IntArray  xRight = getRight(x, floorHalfN);
        IntArray  yLeft = getLeft(y, floorHalfN);
        IntArray  yRight = getRight(y, floorHalfN);

        long p_4 = System.nanoTime();


//        System.out.println(Arrays.toString(xLeft.toArray()));
//        System.out.println(Arrays.toString(xRight.toArray()));
//        System.out.println(Arrays.toString(yLeft.toArray()));
//        System.out.println(Arrays.toString(yRight.toArray()));

        IntArray p1 = karatsuba(xLeft, yLeft, radix);
        IntArray p2 = karatsuba(xRight, yRight, radix);
        IntArray p3 = karatsuba(plus(xLeft, xRight, radix), plus(yLeft, yRight, radix), radix);

        long p_5 = System.nanoTime();

//        System.out.print("p1 = ");
//        System.out.println(Arrays.toString(p1.toArray()));
//        System.out.print("p2 = ");
//        System.out.println(Arrays.toString(p2.toArray()));
//        System.out.print("p3 = ");
//        System.out.println(Arrays.toString(p3.toArray()));

        IntArray r1 = new CompoundIntArray(p1, new SimpleIntArray(new int[2 * floorHalfN]));
        IntArray r2 = plus(plus(p3, negative(p1), radix), negative(p2), radix);
//        List<Byte> r2 = minus(minus(p3, p1, radix), p2, radix);
        IntArray r3 = new CompoundIntArray(r2, new SimpleIntArray(new int[floorHalfN]));

        long p_6 = System.nanoTime();

//        System.out.print("r1 = ");
//        System.out.println(Arrays.toString(r1.toArray()));
//        System.out.print("r2 = ");
//        System.out.println(Arrays.toString(r2.toArray()));
//        System.out.print("r3 = ");
//        System.out.println(Arrays.toString(r3.toArray()));

        IntArray result = plus(plus(r1, r3, radix), p2, radix);

        long p_7 = System.nanoTime();


//        System.out.println("p4 = " + (p_4 - p_1));
//        System.out.println("p5 = " + (p_5 - p_4));
//        System.out.println("p6 = " + (p_6 - p_5));
//        System.out.println("p7 = " + (p_7 - p_6));

//        System.out.println("r = " + Arrays.toString(result.toArray()));

        return result;
    }

    private static long byteArrayNumberToLong(IntArray number, int radix) {
        long result = 0;
        for (int i = 0; i < number.size(); i++) {
            result *= radix;
            result += number.get(i);
        }
        return result;
    }

    private static IntArray longNumberToByteArray(long number, int radix) {
//        IntArray result = new LinkedIntArray();
//        while(number != 0) {
//            result.addFirst((int) (number % radix));
//            number /= radix;
//        }
//        return result;

        List<Integer> result = new ArrayList<Integer>();
        while(number != 0) {
            result.add((int) (number % radix));
            number /= radix;
        }
        int[] array = new int[result.size()];
        for (int i = 0; i < array.length; i++) {
            array[i] = result.get(array.length - i - 1);
        }
        return new SimpleIntArray(array);
    }

    private static IntArray plus(IntArray x, IntArray y, int radix) {
        int lengthDifference = Math.abs(x.size() - y.size());
        if (x.size() > y.size()) {
            y = new CompoundIntArray(new SimpleIntArray(new int[lengthDifference]),  y);
        }
        if (x.size() < y.size()) {
            x = new CompoundIntArray(new SimpleIntArray(new int[lengthDifference]),  x);
        }
        //invariant: y.length == x.length;

        int[] result = new int[x.size()];
        int inMind = 0;
        for (int i = x.size() - 1; i >= 0; i--) {
            int sum = x.get(i) + y.get(i) + inMind;
            int digit = sum % radix;
            if (digit >= 0) {
                result[i] = digit;
                inMind = sum / radix;
            } else {
                result[i] = radix + digit;
                inMind = sum / radix - 1;
            }
        }
        if (inMind != 0) {
            return new CompoundIntArray(new SimpleIntArray(new int[] {inMind}), new SimpleIntArray(result));
        }
        return new SimpleIntArray(result);
    }

    private static IntArray negative(IntArray number) {
        int[] result = new int[number.size()];
        for (int i = 0; i < number.size(); i++) {
            result[i] = - number.get(i);
        }
        return new SimpleIntArray(result);
    }

    private static IntArray getLeft(IntArray number, int rightLength) {
        int bitCount = number.size() - rightLength;
        if (bitCount > 0) {
            return number.subArray(0, bitCount);
        } else {
            return new SimpleIntArray(new int[1]);
        }
    }

    private static IntArray getRight(IntArray number, int rightLength) {
        if (rightLength <= number.size()) {
            return number.subArray(number.size() - rightLength, number.size());
        } else {
            return new CompoundIntArray(new SimpleIntArray(new int[rightLength - number.size()]), number);
        }
    }

    interface IntArray {
        public int get(int index);
        public int size();
        public IntArray subArray(int startIndex, int endIndex);
    }

    static class SimpleIntArray implements IntArray {
        private int[] array;
        private int startIndex;
        private int endIndex;

        public SimpleIntArray(int[] array) {
            this.array = array;
            this.startIndex = 0;
            this.endIndex = array.length;
        }

        SimpleIntArray(int[] array, int startIndex, int endIndex) {
            this.array = array;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        public int get(int index) {
            return array[startIndex + index];
        }

        public int size() {
            return endIndex - startIndex;
        }

        @Override
        public IntArray subArray(int startIndex, int endIndex) {
            return new SimpleIntArray(array, startIndex, endIndex);
        }
    }

    static class CompoundIntArray implements IntArray {
        private IntArray array1;
        private IntArray array2;
        private int startIndex;
        private int endIndex;

        CompoundIntArray(IntArray array1, IntArray array2) {
            this.array1 = array1;
            this.array2 = array2;
            this.startIndex = 0;
            this.endIndex = array1.size() + array2.size();
        }

        CompoundIntArray(IntArray array1, IntArray array2, int startIndex, int endIndex) {
            this.array1 = array1;
            this.array2 = array2;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        public int get(int index) {
            int i = startIndex + index;
            if (i < array1.size()) {
                return array1.get(i);
            } else {
                return array2.get(i - array1.size());
            }
        }

        public int size() {
            return endIndex - startIndex;
        }

        @Override
        public IntArray subArray(int startIndex, int endIndex) {
            return new CompoundIntArray(array1, array2, startIndex, endIndex);
        }
    }

}
